#include "lineDart.h"
#include "randUtil.h"
#include <algorithm>

using namespace std;

LineDart::LineDart()
{
}

LineDart::~LineDart()
{
}

void LineDart::reset(unsigned int d)
{
	dartDimensionIndex_ = RandUtil::randRange(d);
	for (unsigned int i = 0; i < d; ++i)
	{
		if (i == dartDimensionIndex_)
			continue;
		refPoint_[i] = RandUtil::rand0To1();
	}

	intervals_.clear();
	intervals_.push_back(Interval(0, 1));
}

void LineDart::updateIntervals(const vector<VectorD>& points, DATA_TYPE radius)
{
	DATA_TYPE sqRadius = radius * radius;
	for (unsigned int i = 0; i < points.size(); ++i)
	{
		if (intervals_.size() == 0)
			break;

		const VectorD& point = points[i];
		DATA_TYPE distSum = sqRadius;
		for (unsigned int d = 0; d < VectorD::getDimensions(); ++d)
		{
			if (d != dartDimensionIndex_)
			{
				distSum -= (point[d] - refPoint_[d]) * (point[d] - refPoint_[d]);
			}
		}
		if (distSum < 0.f)
			continue;

		DATA_TYPE x0 = point[dartDimensionIndex_] - sqrt(distSum);
		DATA_TYPE x1 = point[dartDimensionIndex_] + sqrt(distSum);
		Interval newInterval(x0, x1);

		list<Interval>::iterator low, up, tempIt;
		low = lower_bound(intervals_.begin(), intervals_.end(), newInterval, Dart::intervalBeginCompare);
		tempIt = low;
		if (tempIt != intervals_.begin())
			--tempIt;
		up = upper_bound(tempIt, intervals_.end(), newInterval, Dart::intervalEndCompare);
		DATA_TYPE min = intervals_.front().begin_;
		DATA_TYPE max = intervals_.back().end_;

		tempIt = up;
		// split an interval
		if (up != intervals_.end() && ++tempIt == low)
		{
			DATA_TYPE splitEnd = up->end_;
			up->end_ = x0;
			intervals_.insert(low, Interval(x1, splitEnd));
		}
		else
		{
			if (x0 > min)
			{
				tempIt = low;
				--tempIt;
				if (x0 < tempIt->end_)
					tempIt->end_ = x0;
			}
			if (x1 < max)
			{
				if (x1 > up->begin_)
					up->begin_ = x1;
			}
			intervals_.erase(low, up);
		}
	}
}

bool LineDart::pickPoint(VectorD& point)
{
	int numIntervals = intervals_.size();
	if (numIntervals == 0)
		return false;

	DATA_TYPE totalLength = 0;
	int i = 0;
	for (list<Interval>::const_iterator it = intervals_.begin(); it != intervals_.end(); ++it)
	{
		totalLength += it->getLength();
		++i;
	}

	DATA_TYPE randPoint = RandUtil::randRange(totalLength);
	i = 0;
	for (list<Interval>::const_iterator it = intervals_.begin(); it != intervals_.end(); ++it)
	{
		DATA_TYPE length = it->getLength();
		if (randPoint <= length)
		{
			refPoint_[dartDimensionIndex_] = it->begin_ + randPoint;
			break;
		}
		randPoint -= length;
		++i;
	}
	if (i == intervals_.size())
		refPoint_[dartDimensionIndex_] = intervals_.back().end_;
	point = refPoint_;

	return true;
}